The technical field of this invention is electronic circuits for communications error correction.
Digital communication systems have developed to a high degree of sophistication in the past two or three decades. Features that, not long ago, could be built into these systems only at enormous expense, can now be deployed in a wide range of applications including consumer electronics. Specifically, error detection and correction (EDAC) techniques, which have long been understood mathematically, were often not practical because of hardware costs. Only simple Hamming Code EDAC""s with single bit correction were practical in low-cost applications. A Reed-Solomon EDAC, on the other hand, uses a powerful encoder/decoder technique that has excellent capability to correct multiple bit errors resulting from high-noise interference environments such as critical space communication, yet are producible at reasonable cost allowing for widespread usage even in moderate-cost products.
Recent advances in electronics have now made high-speed digital data communications prevalent in many types of applications and uses. Digital communication techniques are now used for communication of audio signals for telephony, with video telephony now becoming available in some locations. Digital communication among computers is also prevalent, particularly with the advent of the Internet. Computer-to-computer networking by way of dedicated connections (e.g., local-area networks) and also by way of dial-up connections has also become prevalent in recent years.
The quality of communications carried out in these ways depends upon the accuracy with which the received signals match the transmitted signals. Some types of communications, such as audio communications, can withstand bit loss to a relatively large degree. However, the communication of digital data, especially of executable programs, requires exact fidelity in order to be at all useful. Accordingly, various techniques for the detection and correction of errors in communicated digital bit streams have been developed. Indeed, error correction techniques have effectively enabled digital communications to be carried out over available communication facilities, such as existing telephone lines, despite the error rates inherent in high-frequency communication over these facilities.
Error correction may also be used in applications other than the communication of data and other signals over networks. For example, the retrieval of stored data by a computer from its own magnetic storage devices also typically utilizes error correction techniques to ensure exact fidelity of the retrieved data; such fidelity is essential in the reliable operation of the computer system from executable program code stored in its mass storage devices. Digital entertainment equipment, such as compact disc players, digital audio tape recorders and players, and the like also now typically utilize error correction techniques to provide high fidelity output.
An important class of error detection and error correction techniques is referred to as Reed-Solomon coding, and was originally described: by the Reed-Solomon article entitled: xe2x80x9cPolynomial Codes over Certain Finite Fieldsxe2x80x9d (see reference 1) Reed-Solomon coding uses Galois Field arithmetic, to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block.
Reed-Solomon code based EDACs are used now in many communication systems such as satellites, modems, audio compact discs, and wireless phones. Each one of these systems is defined by a standard. The standard will define the parameters for the Reed-Solomon encoder/decoder. The encoder/decoder. implies an encoder plus a companion decoder. Table 1 below lists a few of those Reed-Solomon parameters for several communication standards. Each communication standard has different values for the parameters which define an Reed-Solomon code.
The parameters xe2x80x9cGalois Fieldxe2x80x9d, xe2x80x9cnxe2x80x9d, xe2x80x9ckxe2x80x9d, xe2x80x9ctxe2x80x9d, and xe2x80x9cp(x)xe2x80x9d will now be described.
Reed-Solomon encoders/decoders use Finite Field arithmetic which is sometimes called Galois Field arithmetic and includes addition, multiplication, division, and exponentiation, in many data processing steps. The rules for such arithmetic operations are completely different from normal binary arithmetic. The primitive polynomial p(x) is used to define the result. The designation GF(X) refers to the number of possible bit combinations of a symbol in a given standard. Thus GF(256) refers to an eight-bit symbol and GF(8) refers to a 3-bit symbol.
Reed-Solomon codes are block codes, meaning that a message at the source is divided into xe2x80x9ckxe2x80x9d blocks of symbols having a designated number of bits xe2x80x9cmxe2x80x9d. For a given system as defined by one of the standards in the table above, for example, two other parameters are used: xe2x80x9cnxe2x80x9d is the number of symbols in a channel codeword, and xe2x80x9ctxe2x80x9d is the number of symbol blocks which can be corrected per each message of k blocks. Thus a particular Reed-Solomon code choice would be represented by: RS(n,k,t). The source codeword, k blocks of symbols, is designated by i(x), and the channel codeword of n blocks of symbols is designated by c(x). The (nxe2x88x92k) excess symbols, called parity symbols, are added to the source word to constitute the codeword, and the number of symbol errors which this system can correct is t=(nxe2x88x92k)/2.
Reed-Solomon encoder/decoders provide forward error correction (FEC) by adding redundancy to the source information. Forward error correction refers to the concept that the receiver does not have an opportunity to communicate with the source. One example of this is the transmitter on a distant planet which cannot interactively communicate with the receiver on earth and make adjustments based on received data (for example, retransmit a new copy of the data which was received and found to be corrupted). The data is transmitted through a non-perfect channel which could introduce errors and is received at the receiver. The Reed-Solomon decoder decodes and corrects the data.
An overall Reed-Solomon encoder/decoder system is shown in FIG. 1. A Reed-Solomon encoder receives and encodes source codeword i(x) including n symbols. The channel codeword c(x) is transmitted by a non-perfect communications channel. The non-perfect channel introduces errors, designated in FIG. 1 by e(x) . The received codeword r(x) has the potential of symbols corruption. Thus the received codeword r(x) may not equal the channel codeword c(x) . The Reed-Solomon decoder does the reverse operation of the Reed-Solomon encoder plus an EDAC function. If there were no errors, the decoded codeword ixe2x80x2(x) would be restored to the same codeword as the source codeword i(x) without need for error correction. Thus:
ixe2x80x2(x)=i(x).
Additionally, if there are symbol errors less than or equal to t in received codeword r(x), then the decoded keyword ixe2x80x2(x) would be also be restored to the same codeword as the source codeword i(x) after error correction. Thus:
ixe2x80x2(x)=i(x).
The Reed-Solomon encoder uses the generator polynomial xcex3(x) in the following equation to generate the channel codeword c(x). The equation of the channel codeword is in systematic form.       C    ⁡          (      x      )        =                    x                  n          -          k                    ⁢              u        ⁡                  (          x          )                      +          REM      ⁡              [                                            x                              n                -                k                                      ⁢                          u              ⁡                              (                x                )                                                          γ            ⁡                          (              x              )                                      ]            
xcex3(x) is defined as:       γ    ⁡          (      x      )        =            ∏              i        =        0                              2          ⁢          t                -        1              ⁢          xe2x80x83        ⁢          (              x        -                  α                      i            +                          j              0                                          )      
j0 is an integer and is used to vary the result of xcex3(x)
The error polynomial is labeled as e(x) and:
r(x)=c(x)+e(x)
The purpose of the Reed-Solomon decoder is to solve for e(x) and calculate ixe2x80x2(x) . If the number of errors added to the block is less than or equal to t, then i (x)=ixe2x80x2(x).
Reed-Solomon encoders/decoders have been built using chip sets consisting of ASIC (Application Specific Integrated circuit) processor elements, DSP (Digital Signal Processor) chips, SRAM (Static Random Access Memory), DRAM (Dynamic Random Access Memory), EPROM (Electrically Programmable Read Only Memory) and other special circuit elements. These types of systems are in wide use in many differentiated products. However design of each variation of these systems calls for extraordinary effort and expense (new ASIC chips, for example) even if they have many similarities to the products being superseded.
FIGS. 2 and 3 illustrate the common features of conventional Reed-Solomon encoder/decoder devices. FIG. 2 illustrates one prior art example of an architecture for a conventional Reed-Solomon encoder. In FIG. 2 each symbol is one eight bit byte in size (i.e., m=8). The example of FIG. 2 uses Galois field arithmetic where the size of the Galois field is 28. In FIG. 2 the maximum codeword length is 28xe2x88x921, or 255 symbols. Other architectures may be used to, derive the encoded codeword for the same message and check symbol coefficients Cz, or for other symbol sizes or other maximum codeword lengths. In the example of FIG. 2, sixteen check symbols are generated for each codeword, thus eight errors per codeword may be corrected. According to conventional Reed-Solomon encoding, the k message bytes in the codeword (Mkxe2x88x921, Mkxe2x88x922, . . . , M0) are used to generate the check symbols (C15, C14, . . . , C0). These check symbols Cz are the coefficients of a polynomial C(x)
C(x)=C15x15+C14x14+ . . . +C0
which is the remainder of the division of a message polynomial M(x) having the message bytes as coefficients:
M(x)=Mkxe2x88x921xkxe2x88x921+Mkxe2x88x922xkxe2x88x922+ . . . +M0
by a divisor referred to as generator polynomial G(x):
G(x)=(x-a0)(x-a1) (x-a2) . . . (x-a15)
where each value ai is a root of the binary primitive polynomial x8+x4+x3+x2+1. The exemplary architecture of FIG. 2 includes sixteen eight-bit shift register latches 220 through 235, which will contain the remainder values from the polynomial division, and thus will produce the check symbol coefficients C15 through C0, respectively. An eight-bit exclusive-OR function 241 through 255 is provided between each pair of shift register latches 220 through 235 to effect Galois field addition, with XOR function 255 located between latches 235 and 234, and so on. The feedback path produced by exclusive-OR function 267, which receives both the input symbol 269 and the output of the last latch 235, presents the quotient for each division step. This quotient is broadcast to sixteen constant Galois field multipliers 265 through 260, which multiply the quotient by respective ones of the coefficients G15 through G0. In operation, the first xe2x80x9ckxe2x80x9d symbols contain the message itself, and are output directly as the leading portion of the codeword. Each of these message symbols, Mz, enters. the encoder architecture of FIG. 2 on IN lines 269, and is applied to the division operation carried out by this encoder. Upon completion of the operations of the architecture of FIG. 2 upon these message bytes, the remainder values retained in shift register latches 235 through 220 correspond to the check symbols C15 through C0, and are appended to the encoded codeword after the xe2x80x9ckxe2x80x9d message symbols.
The encoded codewords are then communicated in a digital bitstream, and communicated in the desired manner, after the appropriate formatting. For communications over telephone facilities the codewords may be communicated either digitally or converted to analog signals; digital network or intra-computer communications will maintain the codewords in their digital format. Regardless of the communications medium, errors may occur in the communicated signals. These errors will be reflected in the received bitstream as opposite binary states from those in the input bitstream prior to the encoding process of FIG. 2. The decoding process seeks to correct these errors. This decoding process will now be described in a general manner relative to FIG. 3.
Decoder 300 of FIG. 3 receives an input bitstream of codeword symbols. A single codeword consists of received codeword r(x) in FIG. 1. Received codeword r(x) is applied to syndrome accumulator 312, which generates a syndrome polynomial s(x) 302 of the form:
s(x)=sIxe2x88x921xIxe2x88x921+sIxe2x88x922Ixe2x88x922+ . . . s1x+s0
Syndrome polynomial s(x) 302 indicates whether errors were introduced into the communicated signals over the communication facility. If s(x)=0, no errors were present. If s(x) is non-zero, one or more errors are present in the codeword under analysis. Syndrome polynomial s(x), in the form of a sequence of coefficients, is then forwarded to Euclidean array block 315.
Euclidean array block 315 generates two polynomials xcex9(x) 303 and xcexa9(x) 304 based upon the syndrome polynomial s(x) 302 received from syndrome accumulator 312. The degree v of polynomial xcex9(x) 303 indicates the number of errors in the codeword. Polynomial xcex9(x) 303 is forwarded to Chien Search block 316 for additional analysis. Polynomial xcexa9(x) 304 is also generated by Euclidean array block 315, and is forwarded to Forney block 318. Forney block 318 uses polynomial xcexa9(x) 304 to evaluate the error in the received bitstream r(x) 301.
Polynomials xcex9(x) 303 is generally referred to as the error locator polynomial. Chien Search block 316 utilizes polynomial xcex9(x) 303 to generate the zeros polynomial "khgr"(x) 305 from which Forney block 318 determines the error magnitude polynomial M(x) 306. Chien Search block 316 also generates polynomial P(x) 307, which indicates the position of the errors in the received codeword r(x) 301. Error Addition block 319 then uses the magnitude of the errors as indicated by polynomial M(x) 306, and the position of these errors as indicated by polynomial P(x) 307 to generate the corrected bitstream ixe2x80x2(x) 308.
This invention relates to programmable, reconfigurable implementations of Reed-Solomon encoder/decoder devices that could be cast into one of three separate designs.
The first design is a stand-alone Reed-Solomon encoder/decoder as illustrated in FIG. 4. This first design includes built-in programmability and reconfigurability through the use of a specially designed Reed-Solomon control block. This Reed-Solomon control block has its own state machine, a bank of special addressable registers, and control logic which allows the user to program and reconfigure the device for a wide variety of applications. The major signals of the stand alone Reed-Solomon encoder/decoder are shown in FIG. 4 and this figure along with FIG. 7 will be used in the text to follow to describe the unique characteristics of this implementation which is the preferred embodiment of this invention.
This first design is supplied with built-in programmability and reconfigurability through the use of the specially designed Reed-Solomon control block. This Reed-Solomon control block has its own state machine, a bank of special addressable registers, a data distribution network, and control logic which allows the user to program and reconfigure the device for a wide variety of applications.
FIG. 5 illustrates the second design of a Reed-Solomon encoder/decoder coprocessor that is to be used with a host DSP or CPU device. This design also allows the user to interface with the host DSP or CPU and program and reconfigure the device for a wide variety of applications. FIG. 5 shows a generic DSP, such as a Texas Instruments TMS320C54. This digital signal processor includes plural execution units. Exponent unit 132 handles exponent manipulation for floating point computations. Multiply/add unit 134 includes a single cycle integer multiplier which may be used in multiply and accumulate operations using accumulators A and B 140. Arithmetic logic unit 136 performs addition, subtraction and logical/compare operations. Barrel shifter 138 performs various shift and rotate operations. Compare select and store unit 142 controls evaluation of conditions for conditional operations and storing results. Execution units 132, 143, 136, 138, 140 and 142 are coupled to memory/peripheral interface 145 via P, C, D and E busses. Memory/peripheral interface controls data exchange with memory and peripherals. Program control and address generator 149 interfaces with an instruction memory space calculating the next instruction address and decoding program instructions for execution via the execution units 132, 143, 136, 138, 140 and 142. Data registers and address generator 148 includes the architected data registers as well as the data address generator. This data address generator calculates the address within a data address space for data reads from and data writes to a data memory. The example illustrated in FIG. 5 includes a random access memory 144 consisting of 6K 16-bit data words and a read only memory 146 consisting of 48K 16-bit instruction words. Those skilled in the art would realize that this illustrated amount of memory represents merely one design example and that more or less memory could be provided as part of the digital signal processor. The digital signal processor includes various system wide services. Phase locked loop clock generator 150 receives an external CLK signal and generates clock control for various parts of the digital signal processor that may include plural clock signals of differing frequencies. Timer 151 is a programmable count-down time used for timing real time events. JTAG test port 152 permits testing of digital signal processor via a serial. scan path in a manner known in the art. Serial and host ports 153 provide connection to various devices external to the digital signal processor. Power distribution 156 provides electric power to the various parts of the digital signal processor. Interface unit 158 provides handshaking to an external memory bus as well as connection to DSP/RS coder interface 160, which controls transmission of data and control signals between the digital signal processor and the Reed-Solomon encoder/decoder.
FIG. 6 illustrates the third design of a custom Reed-Solomon encoder/decoder integrated circuit with an embedded digital signal processor device or CPU device. This design also includes built-in programmability and reconfigurability through the use of the specially designed Reed-Solomon control block. This Reed-Solomon control block has its own state machine, a bank of special addressable registers, a data distribution network, and control logic. This design allows for efficient use in applications implementing not only Reed-Solomon encode/decode but additional processes, which would conventionally make use of a host DSP or CPU and other companion coprocessors. An example would be applications where a convolutional decoder is employed, using Viterbi decoding, convolutional decoding, and other processes. FIG. 6 shows a generic digital signal processor, such as a Texas Instruments TMS320C54, in the same form as illustrated in FIG. 5. The embedded DSP interfaces to the Reed-Solomon encoder/decoder via the xe2x80x9cPxe2x80x9d, xe2x80x9cCxe2x80x9d, and xe2x80x9cDxe2x80x9d busses internal to the DSP. Connection and interaction between the digital signal processor and the Reed-Solomon coprocessor preferably occurs in accordance with the description of U.S. Provisional Patent Application No. 60/073,668 filed Feb. 4, 1998 and entitled DIGITAL SIGNAL PROCESSOR WITH EFFICIENTLY CONNECTABLE HARDWARE CO-PROCESSOR.
All three implementations of this invention are designed for both encoding and decoding, and implement a wide variety of Reed-Solomon codes with a single hardware solution. All the parameters relating to a given system standard are programmable. The encoder and decoder are independent of one another and can be executed in parallel in one unit if both transmitter and receiver are local, that is, a part of the same piece of equipment. The encoder and decoder could be executing completely different Reed-Solomon codes.
The implementation of this invention, as noted above, could be in the form of either a chip set of multiple chips partitioned for best system cost or a fully integrated chip containing all elements of a Reed-Solomon encoder/decoder system. In the most simple form illustrated in FIG. 4 the device would be programmed in its own application board where the reset and setup operations would be carried out. In the second and third designs illustrated in FIGS. 5 and 6, respectively, software would be developed which would be a derivative of that developed for a standard host processor, such as the DSP illustrated in FIGS. 5 and 6, of similar architecture. This software would have all the other code to allow the use of the chip set or single chip of this invention to fully program and fully reconfigure all of the Reed-Solomon encoder/decoder hardware for an extremely wide variety of Reed-Solomon encoder/decoder system applications.
The programming and reconfiguring of the Reed-Solomon encoder/decoder of this invention is straightforward and is reduced to a sequence of operations directed to loading addressable registers with all the necessary information to carry out the encoder or decoder operation completely.